package com.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 47. 全排列 II
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * 示例 1：
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 *  [1,2,1],
 *  [2,1,1]]
 * 示例 2：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 提示：
 * 1 <= nums.length <= 8
 * -10 <= nums[i] <= 10
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年11月23日 11:00
 */
class Code47 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,1,2};
        Code47 code = new Code47();
        List<List<Integer>> permute = code.permuteUnique(nums);
        System.out.println(permute);
    }
    List<List<Integer>> resList = new ArrayList<>();
    List<Integer> tempList = new ArrayList<>();
    boolean[] flag = null;
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        //标记元素是否使用过
        flag = new boolean[nums.length];
        dfs(nums);
        return resList;
    }

    public void dfs(int[] nums){
      if(tempList.size() >= nums.length){
          resList.add(new ArrayList<>(tempList));
          return;
      }
        for (int i = 0; i < nums.length; i++) {
            //nums[i-1] == nums[i]&& !flag[i-1]) : 抽象为树结构，同层元素去重
            //flag[i]：标记使用过的元素，即使用过的不在使用
            if((i>0 && nums[i-1] == nums[i]&& !flag[i-1]) || flag[i]){
                continue;
            }
            tempList.add(nums[i]);
            flag[i] = true;
            dfs(nums);
            tempList.remove(tempList.size()-1);
            flag[i] = false;
        }
    }
}
